package com.August_ThirtyOne;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 946. 验证栈序列
 * 给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/validate-stack-sequences
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Solution946 {
    public static boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> deque=new ArrayDeque<>();
        int j=0;
        for (int i=0;i<pushed.length;i++)
        {
            deque.offer(pushed[i]);
            System.out.println(deque);
            System.out.println(deque.peek());
            while (!deque.isEmpty()&&deque.peekLast()==popped[j])
            {
                j++;
                deque.removeLast();
            }
        }
        return deque.isEmpty();
    }

    public static void main(String[] args) {
        int[] pushed={1,2,3,4,5},poped={4,5,3,2,1};
        System.out.println(validateStackSequences(pushed,poped));
    }
}
